{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sliding Subarray Beauty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getSubarrayBeauty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #滑动子数组的美丽值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;，请你求出每个长度为&nbsp;<code>k</code>&nbsp;的子数组的 <b>美丽值</b>&nbsp;。</p>\n",
    "\n",
    "<p>一个子数组的 <strong>美丽值</strong>&nbsp;定义为：如果子数组中第 <code>x</code>&nbsp;<strong>小整数</strong>&nbsp;是 <strong>负数</strong>&nbsp;，那么美丽值为第 <code>x</code>&nbsp;小的数，否则美丽值为 <code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个包含<em>&nbsp;</em><code>n - k + 1</code>&nbsp;个整数的数组，<strong>依次</strong>&nbsp;表示数组中从第一个下标开始，每个长度为&nbsp;<code>k</code>&nbsp;的子数组的<strong>&nbsp;美丽值</strong>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p>子数组指的是数组中一段连续 <strong>非空</strong>&nbsp;的元素序列。</p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,-1,-3,-2,3], k = 3, x = 2\n",
    "<b>输出：</b>[-1,-2,-2]\n",
    "<b>解释：</b>总共有 3 个 k = 3 的子数组。\n",
    "第一个子数组是 <code>[1, -1, -3]</code> ，第二小的数是负数 -1 。\n",
    "第二个子数组是 <code>[-1, -3, -2]</code> ，第二小的数是负数 -2 。\n",
    "第三个子数组是 <code>[-3, -2, 3]&nbsp;，第二小的数是负数 -2 。</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [-1,-2,-3,-4,-5], k = 2, x = 2\n",
    "<b>输出：</b>[-1,-2,-3,-4]\n",
    "<b>解释：</b>总共有 4 个 k = 2 的子数组。\n",
    "<code>[-1, -2] 中第二小的数是负数 -1 。</code>\n",
    "<code>[-2, -3] 中第二小的数是负数 -2 。</code>\n",
    "<code>[-3, -4] 中第二小的数是负数 -3 。</code>\n",
    "<code>[-4, -5] 中第二小的数是负数 -4 。</code></pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [-3,1,2,-3,0,-3], k = 2, x = 1\n",
    "<b>输出：</b>[-3,0,-3,-3,-3]\n",
    "<b>解释：</b>总共有 5 个 k = 2 的子数组。\n",
    "<code>[-3, 1] 中最小的数是负数 -3 。</code>\n",
    "<code>[1, 2] 中最小的数不是负数，所以美丽值为 0 。</code>\n",
    "<code>[2, -3] 中最小的数是负数 -3 。</code>\n",
    "<code>[-3, 0] 中最小的数是负数 -3 。</code>\n",
    "<code>[0, -3] 中最小的数是负数 -3 。</code></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length&nbsp;</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "\t<li><code>1 &lt;= x &lt;= k&nbsp;</code></li>\n",
    "\t<li><code>-50&nbsp;&lt;= nums[i] &lt;= 50&nbsp;</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sliding-subarray-beauty](https://leetcode.cn/problems/sliding-subarray-beauty/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sliding-subarray-beauty](https://leetcode.cn/problems/sliding-subarray-beauty/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-1,-3,-2,3]\\n3\\n2', '[-1,-2,-3,-4,-5]\\n2\\n2', '[-3,1,2,-3,0,-3]\\n2\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        beautyList = SortedList(nums[:k])\n",
    "        beauty = beautyList[x - 1]\n",
    "        if beauty < 0:\n",
    "            res.append(beauty)\n",
    "        else:\n",
    "            res.append(0)\n",
    "        for i in range(k, n):\n",
    "            beautyList.remove(nums[i-k])\n",
    "            beautyList.add(nums[i])\n",
    "            beauty = beautyList[x-1]\n",
    "            if beauty < 0:\n",
    "                res.append(beauty)\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def getSubarrayBeauty2(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        for i in range(n- k + 1):\n",
    "            beauty = sorted(nums[i:i+k])[x-1]\n",
    "            if beauty < 0:\n",
    "                res.append(beauty)\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "\n",
    "        ans = [min(0, l[x - 1])]\n",
    "        for i in range(k, len(nums)):\n",
    "            l.remove(nums[i - k])\n",
    "            l.add(nums[i])\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "\n",
    "        l = SortedList()\n",
    "\n",
    "        for i in range(k):\n",
    "\n",
    "            l.add(nums[i])\n",
    "\n",
    "        \n",
    "\n",
    "        ans = [min(0, l[x - 1])]\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "\n",
    "            l.remove(nums[i - k])\n",
    "\n",
    "            l.add(nums[i])\n",
    "\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        \n",
    "        ans = [min(0, l[x - 1])]\n",
    "        for i in range(k, len(nums)):\n",
    "            l.remove(nums[i - k])\n",
    "            l.add(nums[i])\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        \n",
    "        ans = [min(0, l[x - 1])]\n",
    "        for i in range(k, len(nums)):\n",
    "            l.remove(nums[i - k])\n",
    "            l.add(nums[i])\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        arr = SortedList()\n",
    "        for num in nums[:k]:\n",
    "            arr.add(num)\n",
    "        res = []\n",
    "        res.append(min(0, arr[x-1]))\n",
    "        for i in range(k, len(nums)):\n",
    "            arr.remove(nums[i - k])\n",
    "            arr.add(nums[i])\n",
    "            res.append(min(0, arr[x-1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n, dct = len(nums), Counter(nums[:k])\n",
    "        def f():\n",
    "            cnt = 0\n",
    "            for y in range(-50, 0):\n",
    "                cnt += dct[y]\n",
    "                if cnt >= x: \n",
    "                    return y\n",
    "            else: return 0\n",
    "        ans = [f()]\n",
    "        for i in range(k, n):\n",
    "            nik, ni = nums[i - k], nums[i]\n",
    "            if nik == ni:\n",
    "                ans.append(ans[-1])\n",
    "            else:\n",
    "                if nik < 0: dct[nik] -= 1\n",
    "                if ni < 0: dct[ni] += 1\n",
    "                ans.append(f())\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        '''\n",
    "        # 二分\n",
    "        lst, n, x = sorted(nums[:k]), len(nums), x - 1\n",
    "        ans = [min(0, lst[x])]\n",
    "        for i in range(k, n):\n",
    "            nik, ni = nums[i - k], nums[i]\n",
    "            if nik != ni:\n",
    "                del lst[bisect.bisect_left(lst, nik)]\n",
    "                j = bisect.bisect(lst, ni)\n",
    "                lst.insert(j, ni)\n",
    "                ans.append(min(0, lst[x]))\n",
    "            else:\n",
    "                ans.append(ans[-1])\n",
    "        return ans\n",
    "        '''\n",
    "\n",
    "        # 暴力\n",
    "        #return [min(0, sorted(nums[i : i + k])[x - 1]) for i in range(len(nums) - k + 1)]\n",
    "\n",
    "        '''\n",
    "        ans = []\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            ans.append(min(0, sorted(nums[i : i + k])[x - 1]))\n",
    "        return ans\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnts = defaultdict(int)\n",
    "        for i in range(k):\n",
    "            cnts[nums[i]] += 1\n",
    "        cnt = 0\n",
    "        res = []   \n",
    "        for cur in sorted(cnts.keys()):\n",
    "            if cur > 0 or cnts[cur] + cnt >= x:\n",
    "                res.append(min(cur, 0))\n",
    "                break\n",
    "            cnt += cnts[cur]\n",
    "        for i in range(k, len(nums)):\n",
    "            cnts[nums[i - k]] -= 1\n",
    "            if (cnts[nums[i - k]] == 0):\n",
    "                cnts.pop(nums[i - k])\n",
    "            cnts[nums[i]] += 1\n",
    "            cnt = 0\n",
    "            # print(cnts)\n",
    "            # print(cnts.keys())\n",
    "            for cur in sorted(cnts.keys()):\n",
    "                if cur > 0 or cnts[cur] + cnt >= x:\n",
    "                    res.append(min(cur, 0))\n",
    "                    break\n",
    "                cnt += cnts[cur]\n",
    "        return res                \n",
    "                                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        ans = []\n",
    "        cnt = defaultdict(int)\n",
    "        \n",
    "        def get_x_min(x: int) -> int:\n",
    "            for num in range(-50, 1):\n",
    "                x -= cnt[num]\n",
    "                if x <= 0: return num\n",
    "            return 0\n",
    "        \n",
    "        \n",
    "        for r in range(len(nums)):\n",
    "            cnt[nums[r]] += 1\n",
    "            if r >= k - 1:\n",
    "                ans.append(get_x_min(x))\n",
    "                cnt[nums[r - (k - 1)]] -= 1 \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        from sortedcontainers import SortedDict\n",
    "        from collections import Counter\n",
    "        d = SortedDict()\n",
    "        ans = [0] * (n - k + 1)\n",
    "        for left in range(n - k + 1):\n",
    "            right = left + k - 1\n",
    "            if left == 0:\n",
    "                d = SortedDict(Counter(nums[left: right + 1]))\n",
    "            else:\n",
    "                d[nums[left - 1]] -= 1\n",
    "                if d[nums[left - 1]] == 0:\n",
    "                    d.pop(nums[left - 1])\n",
    "                d[nums[right]] = d.get(nums[right], 0) + 1\n",
    "            x_ = x\n",
    "            for k_, c in d.items():\n",
    "                x_ -= c\n",
    "                if x_ <= 0:\n",
    "                    ans[left] = min(k_, 0)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        res = []\n",
    "        sl = SortedList([nums[i] for i in range(k) if nums[i] < 0])\n",
    "        res.append(sl[x - 1] if len(sl) >= x else 0)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            if nums[i - k] < 0:\n",
    "                sl.remove(nums[i - k])\n",
    "            if nums[i] < 0:\n",
    "                sl.add(nums[i])\n",
    "\n",
    "            res.append(sl[x - 1] if len(sl) >= x else 0)\n",
    "            \n",
    "        return res\n",
    "\n",
    "            \n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        ans = []\n",
    "        for i, y in enumerate(nums):\n",
    "            sl.add(y)\n",
    "            if i>=k-1:\n",
    "                ans.append(min(sl[x-1],0))\n",
    "                sl.remove(nums[i-k+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        arr=[0]*101\n",
    "        for i in range(k):\n",
    "            idx=nums[i]+50\n",
    "            arr[idx]+=1\n",
    "        ans=[]\n",
    "        cnt=0\n",
    "        for i in range(101):\n",
    "            cnt+=arr[i]\n",
    "            if cnt>=x:\n",
    "                ans.append(i-50)\n",
    "                break\n",
    "        for i in range(1,len(nums)-k+1):\n",
    "            arr[nums[i-1]+50]-=1\n",
    "            arr[nums[i+k-1]+50]+=1\n",
    "            cnt=0\n",
    "            for i in range(101):\n",
    "                cnt += arr[i]\n",
    "                if cnt >= x:\n",
    "                    ans.append(i - 50)\n",
    "                    break\n",
    "        for i in range(len(ans)):\n",
    "            if ans[i]>0:\n",
    "                ans[i]=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        n = len(nums)\n",
    "        for i in range(k-1):\n",
    "            cnt[nums[i]] += 1\n",
    "        res = [0] * (n - k + 1)\n",
    "        for i in range(k-1, n):\n",
    "            cnt[nums[i]] += 1\n",
    "            idx = 0\n",
    "            for j in range(-50, 0):\n",
    "                idx += cnt[j]\n",
    "                if x <= idx:\n",
    "                    res[i-k+1] = j\n",
    "                    break\n",
    "            cnt[nums[i-k+1]]-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[0:k-1]:\n",
    "            cnt[num]+=1\n",
    "        kk = []\n",
    "        for i in range(len(nums)-k+1):\n",
    "            cnt[nums[i+k-1]]+=1\n",
    "            left = 0\n",
    "            for j in range(-50,1):\n",
    "                left+=cnt[j]\n",
    "                if left>=x or j==0:\n",
    "                    kk.append(j)\n",
    "                    break\n",
    "            cnt[nums[i]]-=1\n",
    "        return kk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        res = []\n",
    "        tmp = SortedList(nums[:k])\n",
    "        if tmp[x-1]<0:\n",
    "            res.append(tmp[x-1])\n",
    "        else:\n",
    "            res.append(0)\n",
    "        for i in range(len(nums)-k):\n",
    "            tmp.remove(nums[i])\n",
    "            tmp.add(nums[i+k])\n",
    "            if tmp[x-1]<0:\n",
    "                res.append(tmp[x-1])\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        res = []\n",
    "        sl = SortedList([nums[i] for i in range(k) if nums[i] < 0])\n",
    "        res.append(sl[x - 1] if len(sl) >= x else 0)\n",
    "\n",
    "        for i in range(1, n - k + 1):\n",
    "            if nums[i - 1] < 0:\n",
    "                sl.remove(nums[i - 1])\n",
    "            if nums[i + k - 1] < 0:\n",
    "                sl.add(nums[i + k - 1])\n",
    "\n",
    "            res.append(sl[x - 1] if len(sl) >= x else 0)\n",
    "            \n",
    "        return res\n",
    "\n",
    "            \n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        #解题思路：\n",
    "        #确定当前窗口中的内容，使用单调栈\n",
    "        \n",
    "        n = len(nums)\n",
    "        window = SortedList()\n",
    "        res = []\n",
    "        \n",
    "        for r in range(n):\n",
    "            window.add(nums[r])\n",
    "            if r >= k - 1:\n",
    "                res.append(min(0,window[x - 1]))\n",
    "                window.remove(nums[r - k + 1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        temp = [0] * 101\n",
    "        for i in range(k):\n",
    "            temp[nums[i] + 50] += 1\n",
    "        ans = []\n",
    "\n",
    "        def findX(temp):\n",
    "            cnt, j = 0, 0\n",
    "            while cnt < x and j < 50:\n",
    "                cnt += temp[j]\n",
    "                j += 1\n",
    "            if cnt >= x:\n",
    "                ans.append(j - 51)\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        findX(temp)\n",
    "        for i in range(k, len(nums)):\n",
    "            temp[nums[i-k] + 50] -= 1\n",
    "            temp[nums[i] + 50] += 1\n",
    "            findX(temp)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        st = [0] * (101)\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            st[nums[i] + 50] += 1\n",
    "        count = 0\n",
    "        for j in range(101):\n",
    "            count += st[j]\n",
    "            if count >= x:\n",
    "                ans.append(min(j - 50, 0))\n",
    "                break\n",
    "        for i in range(k, n):\n",
    "            st[nums[i - k] + 50] -= 1\n",
    "            st[nums[i] + 50] += 1\n",
    "            count = 0\n",
    "            for j in range(101):\n",
    "                count += st[j]\n",
    "                if count >= x:\n",
    "                    ans.append(min(j - 50, 0))\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        \n",
    "        ans = [min(0, l[x - 1])]\n",
    "        for i in range(k, len(nums)):\n",
    "            l.remove(nums[i - k])\n",
    "            l.add(nums[i])\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        s = SortedList()\n",
    "        s.update(nums[:k-1])\n",
    "        l, r = 0, k - 1\n",
    "        ans = []\n",
    "        while r < len(nums):\n",
    "            s.add(nums[r])\n",
    "            ans.append(min(s[x-1], 0))\n",
    "            s.remove(nums[l])\n",
    "            l += 1\n",
    "            r += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l=SortedList(nums[:k])\n",
    "\n",
    "        n=len(nums)\n",
    "        ans=[min(0,l[x-1])]\n",
    "        for i in range(k,n):\n",
    "            l.remove(nums[i-k])\n",
    "            l.add(nums[i])\n",
    "         \n",
    "            ans.append(min(0,l[x-1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        res=[]\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        res.append(min(0,l[x-1]))\n",
    "        # print(l)\n",
    "        for i in range(k,len(nums)):\n",
    "            l.remove(nums[i-k])\n",
    "            l.add(nums[i])\n",
    "            # print(l)\n",
    "            res.append(min(0,l[x-1]))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        a = [0] * 101\n",
    "        for v in nums[:k - 1]:\n",
    "            a[v] += 1\n",
    "        \n",
    "        ans = list()\n",
    "        for i in range(k - 1, len(nums)):\n",
    "            a[nums[i]] += 1\n",
    "            c = 0\n",
    "            for j in range(-50, 0):\n",
    "                c += a[j]\n",
    "                if c >= x:\n",
    "                    ans.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(0)\n",
    "            a[nums[i - k + 1]] -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = SortedList()\n",
    "        for i in range(k):\n",
    "            s.add(nums[i])\n",
    "        res = []\n",
    "        y = s[x - 1]\n",
    "        if y >= 0: y = 0\n",
    "        res.append(y)\n",
    "        for i in range(k, n):\n",
    "            s.remove(nums[i - k])\n",
    "            s.add(nums[i])\n",
    "            y = s[x - 1]\n",
    "            if y >= 0:\n",
    "                y = 0\n",
    "            res.append(y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        window = SortedList(nums[:k])\n",
    "        idx = window.bisect_left(0)   # 非负数的第一个位置\n",
    "        ans = [0] if idx < x else [window[x - 1]]\n",
    "        for i in range(k, n):\n",
    "            left = nums[i - k]\n",
    "            window.remove(left)\n",
    "            window.add(nums[i])\n",
    "            idx = window.bisect_left(0)\n",
    "            ans.append(0 if idx < x else window[x - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        beautyList = SortedList(nums[:k])\n",
    "        beauty = beautyList[x - 1]\n",
    "        if beauty < 0:\n",
    "            res.append(beauty)\n",
    "        else:\n",
    "            res.append(0)\n",
    "        for i in range(k, n):\n",
    "            beautyList.remove(nums[i-k])\n",
    "            beautyList.add(nums[i])\n",
    "            beauty = beautyList[x-1]\n",
    "            if beauty < 0:\n",
    "                res.append(beauty)\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        sl = SortedList(nums[: k])\n",
    "        res = [min(sl[x - 1], 0)]\n",
    "\n",
    "        for i in range(k, n):\n",
    "            sl.remove(nums[i - k])\n",
    "            sl.add(nums[i])\n",
    "\n",
    "            res.append(min(sl[x - 1], 0))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "#         temp = [0]*101\n",
    "#         for i in range(k-1):\n",
    "#             temp[nums[i]+50]+=1\n",
    "        \n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[:k - 1]:  # 先往窗口内添加 k-1 个数\n",
    "            cnt[num] += 1\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "            # print(in_, out)\n",
    "            cnt[in_] += 1  # 进入窗口（保证窗口有恰好 k 个数）\n",
    "            left = x\n",
    "            for j in range(-50, 0):  # 暴力枚举负数范围 [-50,-1]\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:  # 找到美丽值\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1  # 离开窗口\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        sl = SortedList()\n",
    "        l, res = 0, []\n",
    "        for r, n in enumerate(nums):\n",
    "            sl.add(n)\n",
    "            if len(sl) > k:\n",
    "                sl.remove(nums[l])\n",
    "                l += 1\n",
    "            if len(sl) == k:\n",
    "                if sl[x - 1] < 0:\n",
    "                    res.append(sl[x - 1])\n",
    "                else:\n",
    "                    res.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        temp_list=SortedList(nums[0:k-1])\n",
    "        result=[]\n",
    "        for i in range(k-1,len(nums)):\n",
    "            temp_list.add(nums[i])\n",
    "            v1=temp_list[x-1]\n",
    "            if v1<0:\n",
    "                result.append(v1)\n",
    "            else:\n",
    "                result.append(0)\n",
    "            temp_list.remove(nums[i-(k-1)])\n",
    "\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        sl = SortedList()\n",
    "        l, res = 0, []\n",
    "        for r, n in enumerate(nums):\n",
    "            sl.add(n)\n",
    "            if len(sl) > k:\n",
    "                sl.remove(nums[l])\n",
    "                l += 1\n",
    "            if len(sl) == k:\n",
    "                if sl[x - 1] < 0:\n",
    "                    res.append(sl[x - 1])\n",
    "                else:\n",
    "                    res.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        container = SortedList()\n",
    "        ans = []\n",
    "        for i in range(k - 1):\n",
    "            container.add(nums[i])\n",
    "        \n",
    "        l = 0\n",
    "        for r in range(k - 1, n):\n",
    "            container.add(nums[r])\n",
    "            if r - l + 1 > k:\n",
    "                container.remove(nums[l])\n",
    "                l += 1\n",
    "            ans.append(min(container[x - 1], 0))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[:k - 1]:  # 先往窗口内添加 k-1 个数\n",
    "            cnt[num] += 1\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "            cnt[in_] += 1  # 进入窗口（保证窗口有恰好 k 个数）\n",
    "            left = x\n",
    "            for j in range(-50, 0):  # 暴力枚举负数范围 [-50,-1]\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:  # 找到美丽值\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1  # 离开窗口\n",
    "        return ans\n",
    "\n",
    "     \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        \n",
    "        ans = [min(0, l[x - 1])]\n",
    "        for i in range(k, len(nums)):\n",
    "            l.remove(nums[i - k])\n",
    "            l.add(nums[i])\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList([])\n",
    "        ans = []\n",
    "        x-=1\n",
    "        for i in range(k-1):\n",
    "            l.add(nums[i])\n",
    "        for i in range(k-1,len(nums)):\n",
    "            l.add(nums[i])\n",
    "            # print(l)\n",
    "            ans.append(l[x] if l[x]<0 else 0)\n",
    "            l.pop(l.index(nums[i-k+1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        sl = SortedList()\n",
    "        for i in range(k):\n",
    "            sl.add(nums[i])\n",
    "        #print(sl)\n",
    "        ans.append(min(0, sl[x - 1]))\n",
    "        \n",
    "        for i in range(k, n):\n",
    "            to_delete_index = sl.bisect_left(nums[i - k])\n",
    "            sl.pop(to_delete_index)\n",
    "            sl.add(nums[i])\n",
    "            ans.append(min(0, sl[x - 1]))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        buc = SortedList( nums[:k])\n",
    "        res = []\n",
    "        for idx in range( len(nums) - k ):\n",
    "            res.append( min(0,buc[x-1]) )\n",
    "            buc.remove( nums[idx] )\n",
    "            buc.add( nums[idx+k] )\n",
    "        res.append( min(0,buc[x-1]) )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        \n",
    "        ans = [min(0, l[x - 1])]\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            l.remove(nums[i - k])\n",
    "            l.add(nums[i])\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        res = []\n",
    "        t = SortedList(nums[0:k])\n",
    "        for i in range(len(nums)-k):\n",
    "            m = t[x-1]\n",
    "            if m < 0:\n",
    "                res.append(m)\n",
    "            else:\n",
    "                res.append(0)\n",
    "            t.remove(nums[i])\n",
    "            t.add(nums[i+k])\n",
    "        if t[x-1] < 0:\n",
    "            res.append(t[x-1])\n",
    "        else:\n",
    "            res.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        def getSecondMin():\n",
    "            t = x\n",
    "            for i, v in enumerate(cnt):\n",
    "                if v >= t:\n",
    "                    return i - 50 if i <= 50 else 0\n",
    "                t -= v\n",
    "            return 0\n",
    "            \n",
    "        ans = []\n",
    "        l = r = 0\n",
    "        cnt = [0] * 110\n",
    "        while r < len(nums):\n",
    "            cnt[nums[r] + 50] += 1\n",
    "            if r - l + 1 == k:\n",
    "                ans.append(getSecondMin())\n",
    "                cnt[nums[l] + 50] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        # 求数组区间最小值\n",
    "        n = len(nums)\n",
    "        i, cnt = 0, defaultdict(int)\n",
    "        ans = []\n",
    "        for j, num in enumerate(nums):\n",
    "            # 判断窗口长度\n",
    "            cnt[num] += 1\n",
    "            while j - i + 1 > k:\n",
    "                cnt[nums[i]] -= 1\n",
    "                if cnt[nums[i]] == 0:\n",
    "                    del cnt[nums[i]]\n",
    "                i += 1\n",
    "            t = x\n",
    "            if j - i + 1 == k:\n",
    "                for a in range(-50, 51):\n",
    "                    if a in cnt:\n",
    "                        if cnt[a] >= t:\n",
    "                            ans.append(min(0, a))\n",
    "                            break\n",
    "                        else:\n",
    "                            t -= cnt[a]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        \n",
    "        ans = [min(0, l[x - 1])]\n",
    "        for i in range(k, len(nums)):\n",
    "            l.remove(nums[i - k])\n",
    "            l.add(nums[i])\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        for i in range(k - 1):\n",
    "            sl.add(nums[i])\n",
    "        ans = []\n",
    "        for i in range(k - 1, len(nums)):\n",
    "            sl.add(nums[i])\n",
    "            ans.append(min(sl[x - 1], 0))\n",
    "            sl.remove(nums[i - k + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        #1、创建一个有序的容器\n",
    "        #2、创建一个结果数组，并且把第x小的数放进去，如果这个数是负的，那么就返回本身，如果是正的就返回0\n",
    "        #3、把第一个数字出来，后面的一个数放进去，再重复执行上面的操作\n",
    "        l=SortedList()\n",
    "        res=[]\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        if l[x-1]<0:\n",
    "            res.append(l[x-1])\n",
    "        else:\n",
    "            res.append(0)\n",
    "        for i in range(k,len(nums)):\n",
    "            l.remove(nums[i-k])\n",
    "            l.add(nums[i])\n",
    "            res.append(min(0,l[x-1]))\n",
    "        return res        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        def getXMin():\n",
    "            t = x\n",
    "            for i, v in enumerate(cnt):\n",
    "                if v >= t:\n",
    "                    return i - 50 if i <= 50 else 0\n",
    "                t -= v\n",
    "            return 0\n",
    "            \n",
    "        ans = []\n",
    "        l = r = 0\n",
    "        cnt = [0] * 110\n",
    "        while r < len(nums):\n",
    "            cnt[nums[r] + 50] += 1\n",
    "            if r - l + 1 == k:\n",
    "                ans.append(getXMin())\n",
    "                cnt[nums[l] + 50] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cnt = [0]*101\n",
    "        ans = [0]*(n-k+1)\n",
    "        for i in range(k):\n",
    "            cnt[nums[i]] += 1\n",
    "        for i in range(n-k+1):\n",
    "            left = x\n",
    "            for j in range(-50, 0):\n",
    "                left -= cnt[j]\n",
    "                if left<=0:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[nums[i]] -= 1\n",
    "            if i+k<n:\n",
    "                cnt[nums[i+k]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        result = []\n",
    "        n = len(nums)\n",
    "        sorted_list = [0]*101\n",
    "        for i in range(k):\n",
    "            sorted_list[nums[i]+50] += 1\n",
    "        def getValue(x):\n",
    "            for i in range(101):\n",
    "                if(sorted_list[i] == 0):\n",
    "                    continue\n",
    "                elif(x <= sorted_list[i]):\n",
    "                    return min(i - 50,0)\n",
    "                else:\n",
    "                    x -= sorted_list[i]\n",
    "        result.append(getValue(x))\n",
    "        for i in range(k,n):\n",
    "            sorted_list[nums[i-k]+50] -= 1\n",
    "            sorted_list[nums[i]+50] += 1\n",
    "            result.append(getValue(x))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        cnt = [0] * 51\n",
    "        for i in range(k):\n",
    "            if nums[i] < 0:\n",
    "                cnt[-nums[i]] += 1\n",
    "\n",
    "        res = []\n",
    "\n",
    "        m = x\n",
    "        for i in range(50, 0, -1):\n",
    "            if cnt[i] > 0:\n",
    "                if cnt[i] >= m:\n",
    "                    res.append(-i)\n",
    "                    break\n",
    "                m -= cnt[i]\n",
    "        else:\n",
    "            res.append(0)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            if nums[i - k] < 0:\n",
    "                cnt[-nums[i - k]] -= 1\n",
    "            if nums[i] < 0:\n",
    "                cnt[-nums[i]] += 1\n",
    "\n",
    "            m = x\n",
    "            for i in range(50, 0, -1):\n",
    "                if cnt[i] > 0:\n",
    "                    if cnt[i] >= m:\n",
    "                        res.append(-i)\n",
    "                        break\n",
    "                    m -= cnt[i]\n",
    "            else:\n",
    "                res.append(0)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        sl,res = SortedList(),[]\n",
    "        for i,num in enumerate(nums):\n",
    "            sl.add(num)\n",
    "            if i >= k:\n",
    "                sl.remove(nums[i-k])\n",
    "            if len(sl) == k:\n",
    "                res.append(0 if sl[x-1]>=0 else sl[x-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        que = SortedList()\n",
    "        for i, num in enumerate(nums[:k]):\n",
    "            que.add(num)\n",
    "        ret = [0 if que[x - 1] > 0 else que[x - 1]]\n",
    "        for i in range(k, len(nums)):\n",
    "            que.remove(nums[i - k])\n",
    "            que.add(nums[i])\n",
    "            if que[x - 1] > 0:\n",
    "                ret.append(0)\n",
    "            else:\n",
    "                ret.append(que[x - 1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cnt = [0] * 101\n",
    "        for i in range(k):\n",
    "            cnt[nums[i] + 50] += 1\n",
    "        \n",
    "        res = []\n",
    "        def check(cnt):\n",
    "            s = 0\n",
    "            for i in range(101):\n",
    "                s += cnt[i]\n",
    "                if s >= x:\n",
    "                    return i - 50\n",
    "        y = check(cnt)\n",
    "        if y >= 0: y = 0\n",
    "        res.append(y)\n",
    "        for i in range(k, n):\n",
    "            cnt[nums[i - k] + 50] -= 1\n",
    "            cnt[nums[i] + 50] += 1\n",
    "            y = check(cnt)\n",
    "            if y >= 0: y = 0\n",
    "            res.append(y)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = SortedList()\n",
    "        for i in range(k):\n",
    "            l.add(nums[i])\n",
    "        \n",
    "        ans = [min(0, l[x - 1])]\n",
    "        for i in range(k, len(nums)):\n",
    "            l.remove(nums[i - k])\n",
    "            l.add(nums[i])\n",
    "            ans.append(min(0, l[x - 1]))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        temp=SortedList()\n",
    "        for i in range(k):\n",
    "            temp.add(nums[i])\n",
    "        res=[min(0,temp[x-1])]\n",
    "        for i in range(k,n):\n",
    "            temp.remove(nums[i-k])\n",
    "            temp.add(nums[i])\n",
    "            res.append(min(0,temp[x-1]))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        l = 0\n",
    "        r = k\n",
    "        sz = len(nums)\n",
    "        cnt = [0] * 101\n",
    "        for n in nums[:k]:\n",
    "            cnt[n] += 1\n",
    "        c = 0\n",
    "        for i in range(-50, 51):\n",
    "            c += cnt[i]\n",
    "            if c >= x:\n",
    "                ans = [min(i, 0)]\n",
    "                break\n",
    "        while r < sz:\n",
    "            cnt[nums[r]] += 1\n",
    "            cnt[nums[l]] -= 1\n",
    "            l += 1\n",
    "            r += 1\n",
    "            \n",
    "            c = 0\n",
    "            for i in range(-50, 51):\n",
    "                c += cnt[i]\n",
    "                if c >= x:\n",
    "                    ans.append(min(i, 0))\n",
    "                    break\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        freq = [0] * 101\n",
    "        l, r = 0, 0\n",
    "        n = len(nums)\n",
    "        res = [0] * (n - k + 1)\n",
    "        i = 0\n",
    "        while r < n:\n",
    "            freq[nums[r]] += 1\n",
    "            while r - l + 1 > k:\n",
    "                freq[nums[l]] -= 1\n",
    "                l += 1\n",
    "            if r - l + 1 == k:\n",
    "                tmp = x\n",
    "                for j in range(-50, 0):\n",
    "                    tmp -= freq[j]\n",
    "                    if tmp <= 0:\n",
    "                        res[i] = j\n",
    "                        break\n",
    "                i += 1\n",
    "            r += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cnt = [0] * 101\n",
    "        \n",
    "        def xth(x):\n",
    "            for i in range(101):\n",
    "                x -= cnt[i]\n",
    "                if x <= 0:\n",
    "                    # print(i - 50, cnt[i])\n",
    "                    return min(0, i - 50)\n",
    "                \n",
    "        for i in nums[:k]:\n",
    "            cnt[i + 50] += 1\n",
    "        ret = [0] * (n - k + 1)\n",
    "        ret[0] = xth(x)\n",
    "        # print(cnt)\n",
    "        for i in range(k, n):\n",
    "            cnt[nums[i] + 50] += 1\n",
    "            cnt[nums[i - k] + 50] -= 1\n",
    "            ret[i - k + 1] = xth(x)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            cnt[nums[i]] += 1\n",
    "            while i - l + 1 > k:\n",
    "                cnt[nums[l]] -= 1\n",
    "                l += 1\n",
    "            if i - l + 1 == k:\n",
    "                t = 0\n",
    "                match = False\n",
    "                for j in range(-50, 0):\n",
    "                    t += cnt[j]\n",
    "                    if t >= x:\n",
    "                        res.append(j)\n",
    "                        match = True\n",
    "                        break\n",
    "                if not match:\n",
    "                    res.append(0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        def getX(tot):\n",
    "            for num in range(-50, 0):\n",
    "                tot -= cnt[num]\n",
    "                if tot <= 0:\n",
    "                    return num \n",
    "            return 0\n",
    "\n",
    "        ret, cnt = [0] * (len(nums) - k + 1), [0] * 101\n",
    "        for i, num in enumerate(nums[:k - 1]):\n",
    "            cnt[num] += 1\n",
    "        for i, (_in, _out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "            cnt[_in] += 1\n",
    "            tot = x\n",
    "            ret[i] = getX(tot)\n",
    "            cnt[_out] -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        countList = [0 for _ in range(101)]\n",
    "        for num in nums[:k]:\n",
    "            countList[num + 50] += 1\n",
    "        left, right = 0, k - 1\n",
    "        ans = []\n",
    "        def getBeauty(lst,x):\n",
    "            index = 0\n",
    "            for i in range(len(lst)):\n",
    "                index += lst[i]\n",
    "                if index >= x:\n",
    "                    return min(i - 50,0)\n",
    "                \n",
    "        while right < len(nums) - 1:\n",
    "            ans.append(getBeauty(countList,x))           \n",
    "            countList[nums[left] + 50] -= 1\n",
    "            left += 1\n",
    "            right += 1\n",
    "            countList[nums[right] + 50] += 1\n",
    "        \n",
    "        ans.append(getBeauty(countList,x))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cnt = [0] * 101\n",
    "        for i in range(0, k-1):\n",
    "            cnt[nums[i]] += 1\n",
    "        \n",
    "        ret = [0] * (n - k + 1)\n",
    "        for i in range(k-1, n):\n",
    "            in_, out_ = nums[i], nums[i - k + 1]\n",
    "            cnt[in_] += 1\n",
    "            tmp = x \n",
    "            for j in range(-50, 0):\n",
    "                tmp -= cnt[j]\n",
    "                if tmp <= 0:\n",
    "                    ret[i-k+1] = j\n",
    "                    break\n",
    "            cnt[out_] -= 1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cntr=Counter()\n",
    "        n,l=len(nums),0\n",
    "        ans=[0]*(n-k+1)\n",
    "        for i,v in enumerate(nums):\n",
    "            cntr[v]+=1\n",
    "            if i-k+1==l:\n",
    "                s=0\n",
    "                for j in range(-50,51):\n",
    "                    if j>0: break\n",
    "                    if cntr[j]+s>=x and j<0:\n",
    "                        ans[l]=j\n",
    "                        break\n",
    "                    s+=cntr[j]\n",
    "                cntr[nums[l]]-=1\n",
    "                l+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[:k - 1]:  # 先往窗口内添加 k-1 个数\n",
    "            cnt[num] += 1\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "            cnt[in_] += 1  # 进入窗口（保证窗口有恰好 k 个数）\n",
    "            left = x\n",
    "            for j in range(-50, 0):  # 暴力枚举负数范围 [-50,-1]\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:  # 找到美丽值\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1  # 离开窗口\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 50\n",
    "        n = len(nums)\n",
    "        ans = [0] * (n - k + 1)\n",
    "        for i in range(k - 1):\n",
    "            if nums[i] < 0:\n",
    "                cnt[nums[i]] += 1\n",
    "        for i in range(n - k + 1):\n",
    "            if nums[i + k - 1] < 0:\n",
    "                cnt[nums[i + k - 1]] += 1\n",
    "            s = x\n",
    "            for j in range(-50, 0, 1):\n",
    "                if s > cnt[j]:\n",
    "                    s -= cnt[j]\n",
    "                else:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            if nums[i] < 0:\n",
    "                cnt[nums[i]] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101 # [-50 ~ 0 ~ 50]\n",
    "        # 统计前k个数\n",
    "        for v in nums[:k-1]:\n",
    "            cnt[v] += 1\n",
    "        \n",
    "        b = []\n",
    "        # 保持k个子数组的滑动窗口\n",
    "        for r in range(k-1, len(nums)):\n",
    "            l = r - k + 1 # k[l:r]\n",
    "            # 先计数 k子数组\n",
    "            cnt[nums[r]] += 1\n",
    "            # 找 值小于 0 的第x小数，如果没找到则b插入0，找到就插入到b末尾\n",
    "            left = x\n",
    "            min_x = 0\n",
    "            for i in range(-50, 0):\n",
    "                left -= cnt[i]\n",
    "                if left <= 0:\n",
    "                    # 找到第x小数的值\n",
    "                    min_x = i\n",
    "                    break\n",
    "            \n",
    "            b.append(min_x)\n",
    "            cnt[nums[l]] -= 1 # 维持下一次k个子数组的统计\n",
    "\n",
    "        return b\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        # 滑动窗口 / 空间优化 / 暴力搜索\n",
    "        n = len(nums)\n",
    "\n",
    "        res = [0] * (n - k + 1)\n",
    "        cnt = [0] * 101\n",
    "\n",
    "        for num in nums[:k-1]:\n",
    "            cnt[num] += 1\n",
    "        \n",
    "        for i , (out, _in) in enumerate(zip(nums, nums[k-1:])):\n",
    "            cnt[_in] += 1\n",
    "            left = x\n",
    "            for j in range(-50, 0):\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:\n",
    "                    res[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt=[0]*101\n",
    "        for n in nums[:k-1]:\n",
    "            cnt[n]+=1\n",
    "        n=len(nums)\n",
    "        ans=[0]*(n-k+1)\n",
    "        n=len(nums)\n",
    "        for i,(_in,_out) in enumerate(zip(nums[k-1:],nums)):\n",
    "            cnt[_in]+=1\n",
    "            left=x\n",
    "            for j in range(-50,0):\n",
    "                left-=cnt[j]\n",
    "                if left<=0:\n",
    "                    ans[i]=j\n",
    "                    break\n",
    "            cnt[_out]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        cnt=[0]*101\n",
    "        ans=[0]*(n-k+1)\n",
    "        for i in nums[:k-1]:\n",
    "            cnt[i]+=1\n",
    "        tmp=nums[:k-1]\n",
    "        for i,(out,in_) in enumerate(zip(nums,nums[k-1:])):\n",
    "            cnt[in_]+=1\n",
    "            lim=x   #至少要有x个负数才满足题目要求\n",
    "            for j in range(-50,0):\n",
    "                lim-=cnt[j]\n",
    "                if lim<=0:\n",
    "                    ans[i]=j\n",
    "                    break\n",
    "            cnt[out]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[:k - 1]:  # 先往窗口内添加 k-1 个数\n",
    "            cnt[num] += 1\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "            cnt[in_] += 1  # 进入窗口（保证窗口有恰好 k 个数）\n",
    "            left = x\n",
    "            for j in range(-50, 0):  # 暴力枚举负数范围 [-50,-1]\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:  # 找到美丽值\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1  # 离开窗口\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        # cnt = [0] * 101\n",
    "        # for num in nums[:k - 1]: # 先往窗口内添加k-1个数\n",
    "        #     cnt[num] += 1 \n",
    "        # ans = [0] * (len(nums) - k + 1)\n",
    "        # for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "        #     cnt[in_] += 1 # 进入窗口(保证窗口恰好k个数)\n",
    "        #     left = x\n",
    "        #     for j in range(-50, 0): #暴力枚举负数范围[-50, -1]\n",
    "        #         left -= cnt[j]\n",
    "        #         if left <= 0: # 找到美丽值\n",
    "        #             ans[i] = j\n",
    "        #             break\n",
    "        #     cnt[out] -= 1 # 离开窗口\n",
    "        # return ans\n",
    "\n",
    "        # 子数组第x小的数字为负，美丽值为该位数字，否则为0，返回所有子数组的美丽值\n",
    "        cnt =[0] * 101\n",
    "        for num in nums[:k -1]:\n",
    "            cnt[num] += 1\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "            cnt[in_] += 1\n",
    "            left = x \n",
    "            for j in range(-50, 0):\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:\n",
    "                    ans[i] = j\n",
    "                    break \n",
    "            cnt[out] -= 1 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.n = n\n",
    "        self.tr = [0] * n\n",
    "        \n",
    "    def lowbit(self, x: int) -> int:\n",
    "        return x & -x\n",
    "    \n",
    "    def update(self, x: int, c: int) -> None:\n",
    "        i = x\n",
    "        while i < self.n:\n",
    "            self.tr[i] += c\n",
    "            i += self.lowbit(i)\n",
    "    \n",
    "    def query(self, x: int) -> int:\n",
    "        res = 0\n",
    "        i = x\n",
    "        while i:\n",
    "            res += self.tr[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        N, P = 110, 51\n",
    "        tree = Tree(N)\n",
    "        res = []\n",
    "        for i, v in enumerate(nums):\n",
    "            tree.update(v + P, 1)\n",
    "            if i > k - 1:\n",
    "                tree.update(nums[i - k] + P, -1)\n",
    "            if i >= k - 1:\n",
    "                l, r = 0, N\n",
    "                while l < r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if tree.query(mid) >= x:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                t = r - P\n",
    "                res.append(t if t < 0 else 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        #解题思路：\n",
    "        #解析：\n",
    "        #利用nums[i]取值范围较少，采用了哈希表进行求解\n",
    "        \n",
    "        n = len(nums)\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[:k - 1]: #先往窗口添加k - 1个元素\n",
    "            cnt[num + 50] += 1 #nums[i]取值范围为-50，50\n",
    "        \n",
    "        res = [0] * (n - k + 1)\n",
    "        for i,(l,r) in enumerate(zip(nums,nums[k - 1:])):\n",
    "            cnt[r + 50] += 1 #进入窗口，保证窗口恰有k个数\n",
    "            left = x \n",
    "            for j in range(50):\n",
    "                left -= cnt[j]\n",
    "                if left <= 0: #找到美丽值\n",
    "                    res[i] = j - 50\n",
    "                    break\n",
    "            cnt[l + 50] -= 1 #离开窗口\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[: k - 1]:\n",
    "            cnt[num] += 1\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "            cnt[in_] += 1\n",
    "            left = x\n",
    "            for j in range(-50, 0):\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[:k-1]:\n",
    "            cnt[num] += 1\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        for i, (in_, out) in enumerate(zip(nums[k-1:],nums)):\n",
    "            cnt[in_] += 1\n",
    "            left = x\n",
    "            for j in range(-50,0):\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        c = [0]*102\n",
    "        n = len(nums)\n",
    "        ans = [0]*(n-k+1)\n",
    "        for i in nums[:k-1]:\n",
    "            c[i+50]+=1\n",
    "        for j,(_in,out) in enumerate(zip(nums[k-1:],nums)):\n",
    "            c[_in+50]+=1\n",
    "            cur = x\n",
    "            for i in range(0,50):\n",
    "                cur -= c[i]\n",
    "                if cur<=0:\n",
    "                    ans[j]=i-50\n",
    "                    break\n",
    "            c[out+50]-=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        #copy 0x3\n",
    "        cnt = [0]*101\n",
    "        for num in nums[:k-1]:\n",
    "            cnt[num] +=1\n",
    "        ans = [0] *(len(nums)-k+1)\n",
    "        for i ,(in_,out) in enumerate(zip(nums[k-1:],nums)):\n",
    "            cnt[in_] += 1\n",
    "            left =x\n",
    "            for j in range(-50,0):\n",
    "                left -= cnt[j]\n",
    "                if left<=0:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1\n",
    "        return ans \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0]*(n-k+1)\n",
    "        cnt = [0]*101\n",
    "        for i in nums[:k-1]:\n",
    "            cnt[i] += 1\n",
    "        for i, (in_, out) in enumerate(zip(nums[k-1:], nums)):\n",
    "            cnt[in_] += 1\n",
    "            l = x\n",
    "            for j in range(-50,0):\n",
    "                l -= cnt[j]\n",
    "                if l <= 0:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101 # 注意题目值的范围!!!\n",
    "        for num in nums[:k-1]: # 记录前k-1个数\n",
    "            cnt[num]+=1\n",
    "        ans = [0] * (len(nums)-k+1)\n",
    "\n",
    "        for i, (in_, out) in enumerate(zip(nums[k-1:],nums)): # 遍历进入滑动窗口和出去的值, Python这种方法真的非常巧妙\n",
    "            cnt[in_]+=1 \n",
    "            left = x\n",
    "            for j in range(-50,0): # 题目要求第x小的数是负数的时候记录, 否则为0, 所以只遍历负数\n",
    "                left-=cnt[j]\n",
    "                if left<=0:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        for num in nums[:k - 1]:  # 先往窗口内添加 k-1 个数\n",
    "            cnt[num] += 1\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):\n",
    "            cnt[in_] += 1  # 进入窗口（保证窗口有恰好 k 个数）\n",
    "            left = x\n",
    "            for j in range(-50, 0):  # 暴力枚举负数范围 [-50,-1]\n",
    "                left -= cnt[j]\n",
    "                if left <= 0:  # 找到美丽值\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "            cnt[out] -= 1  # 离开窗口\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
